import java.util.Arrays;

/**
 * @Author: LI DUO
 * @Date: 2019/4/24 下午 10:15
 * @Version 1.0
 * 189. 旋转数组
 */
public class Rotate {
    public void rotate(int[] nums, int k) {
        while (k > 0) {
            int j = nums[nums.length - 1];
            for (int i = nums.length - 1; i > 0; i--) {
                nums[i] = nums[i - 1];
            }
            nums[0] = j;
            k--;
        }
    }

    public void rotate2(int[] nums, int k) {
        if (k > nums.length) {
            k = k % nums.length;
        }
        while (k > 0) {
            int j = nums[nums.length - 1];
            System.arraycopy(nums, 0, nums, 1, nums.length - 1);
            nums[0] = j;
            k--;
        }
    }

    /**
     * 翻转
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public void rotate_2(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }


    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }

    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3, 4, 5, 6, 7};
        Rotate rotate = new Rotate();
        rotate.rotate(a, 3);
        System.out.println(Arrays.toString(a));
    }
}
